#include <iostream>
#include "binary_tree.h"

BinaryTreeNode* CreateBinaryTreeNode(int value) {
  BinaryTreeNode* node = new BinaryTreeNode();
  node->value = value;
  node->left = nullptr;
  node->right = nullptr;
  return node;
}

BinaryTreeWithParentNode* CreateBinaryTreeWithParentNode(int value) {
  BinaryTreeWithParentNode* node = new BinaryTreeWithParentNode();
  node->value = value;
  node->parent = nullptr;
  node->left = nullptr;
  node->right = nullptr;
  return node;
}

void ConnectNode(BinaryTreeNode* parent, BinaryTreeNode* left, BinaryTreeNode* right) {
  if (parent) {
    parent->left = left;
    parent->right = right;
  }
}

void ConnectNode(BinaryTreeWithParentNode* parent, BinaryTreeWithParentNode* left, BinaryTreeWithParentNode* right) {
  if (parent) {
    parent->left = left;
    parent->right = right;
    if (left) {
      left->parent = parent;
    }
    if (right) {
      right->parent = parent;
    }
  }
}

BinaryTreeNode* CreateBinaryTree(std::vector<int> nodes_vec) {
    if (nodes_vec.empty()) {
        std::cout << "input binary tree is null" << std::endl;
        return nullptr;
    }
    std::vector<BinaryTreeNode*> binary_tree_vec;
    BinaryTreeNode* new_node = new BinaryTreeNode();
    new_node->value = nodes_vec[0];
    binary_tree_vec.push_back(new_node);
    for (size_t i = 1; i < nodes_vec.size(); i++) {
        if (nodes_vec[i] != -1) {
            BinaryTreeNode* new_node = new BinaryTreeNode();
            new_node->value = nodes_vec[i];
            binary_tree_vec.push_back(new_node);
            int index = (i + 1) / 2 - 1;
            if ((i + 1) % 2 == 0) {
                binary_tree_vec[index]->left = new_node;
            }
            if ((i + 1) % 2 != 0) {
                binary_tree_vec[index]->right = new_node;
            }
        }
    }
    return new_node;
}

BinaryTreeWithParentNode* CreateBinaryTreeWithParentNode(std::vector<int> nodes_vec) {
    if (nodes_vec.empty()) {
        std::cout << "input binary tree is null" << std::endl;
        return nullptr;
    }
    std::vector<BinaryTreeWithParentNode*> binary_tree_vec;
    BinaryTreeWithParentNode* new_node = new BinaryTreeWithParentNode();
    new_node->value = nodes_vec[0];
    new_node->parent = nullptr;
    new_node->left = nullptr;
    new_node->right = nullptr;
    binary_tree_vec.push_back(new_node);
    for (size_t i = 1; i < nodes_vec.size(); i++) {
        if (nodes_vec[i] != -1) {
            BinaryTreeWithParentNode* new_node = new BinaryTreeWithParentNode();
            new_node->value = nodes_vec[i];
            new_node->parent = nullptr;
            new_node->left = nullptr;
            new_node->right = nullptr;
            binary_tree_vec.push_back(new_node);
            int index = (i + 1) / 2 - 1;
            if ((i + 1) % 2 == 0) {
                binary_tree_vec[index]->left = new_node;
                new_node->parent = binary_tree_vec[index];
            }
            if ((i + 1) % 2 != 0) {
                binary_tree_vec[index]->right = new_node;
                new_node->parent = binary_tree_vec[index];
            }
        }
    }
    return new_node;
}

void PrintBinaryTreeNode(BinaryTreeNode* node) {
  if (node) {
    std::cout << "cur_node: " << node->value << " ";
    if (node->left) {
      std::cout << "left_node: " << node->left->value << " ";
    } else {
      std::cout << "left_node: nullptr" << " ";
    }
    if (node->right) {
      std::cout << "right_node: " << node->right->value << std::endl;
    } else {
      std::cout << "right_node: nullptr" << std::endl;
    }
  }
}

void PrintBinaryTreeNode(BinaryTreeWithParentNode* node) {
  if (node) {
    std::cout << "cur_node: " << node->value << " ";
    if (node->left) {
      std::cout << "left_node: " << node->left->value << " ";
    } else {
      std::cout << "left_node: nullptr" << " ";
    }
    if (node->right) {
      std::cout << "right_node: " << node->right->value << std::endl;
    } else {
      std::cout << "right_node: nullptr" << std::endl;
    }
  }
}

void PrintBinaryTree(BinaryTreeNode* root) {
    if (!root) {
        std::cout << "input binary tree is null" << std::endl;
        return;
    }
    std::deque<BinaryTreeNode*> dequeTreeNode;
    dequeTreeNode.push_back(root);
    std::cout << root->value << std::endl;

    int prelevel = 1, nextlevel = 0;
    while (!dequeTreeNode.empty()) {
        BinaryTreeNode* node = dequeTreeNode.front();
        if (node->left) {
            dequeTreeNode.push_back(node->left);
            nextlevel++;
            std::cout << node->left->value << " ";
        }
        if (node->right) {
            dequeTreeNode.push_back(node->right);
            nextlevel++;
            std::cout << node->right->value << " ";
        }
        dequeTreeNode.pop_front();
        prelevel--;
        if (prelevel == 0) {
            std::cout << std::endl;
            prelevel = nextlevel;
            nextlevel = 0;
        }
    }
}

void PrintBinaryTree(BinaryTreeWithParentNode* root) {
    if (!root) {
        std::cout << "input binary tree is null" << std::endl;
        return;
    }
    std::deque<BinaryTreeWithParentNode*> dequeTreeNode;
    dequeTreeNode.push_back(root);
    std::cout << root->value << std::endl;

    int prelevel = 1, nextlevel = 0;
    while (!dequeTreeNode.empty()) {
        BinaryTreeWithParentNode* node = dequeTreeNode.front();
        if (node->left) {
            dequeTreeNode.push_back(node->left);
            nextlevel++;
            std::cout << node->left->value << " ";
        }
        if (node->right) {
            dequeTreeNode.push_back(node->right);
            nextlevel++;
            std::cout << node->right->value << " ";
        }
        dequeTreeNode.pop_front();
        prelevel--;
        if (prelevel == 0) {
            std::cout << std::endl;
            prelevel = nextlevel;
            nextlevel = 0;
        }
    }
}

void DeleteBinaryTree(BinaryTreeNode* root) {
    if (root) {
        BinaryTreeNode* left = root->left;
        BinaryTreeNode* right = root->right;
        delete root;
        root = nullptr;
        DeleteBinaryTree(left);
        DeleteBinaryTree(right);
    }
}

void DeleteBinaryTree(BinaryTreeWithParentNode* root) {
    if (root) {
        BinaryTreeWithParentNode* left = root->left;
        BinaryTreeWithParentNode* right = root->right;
        delete root;
        root = nullptr;
        DeleteBinaryTree(left);
        DeleteBinaryTree(right);
    }
}
